package leetcode.code1894;

public class Solution extends Solution1894 {

	@Override
	public int chalkReplacer(int[] chalk, int k) {
		int len = chalk.length;
		int left = 0;
		int right = len - 1;
		for (int i = 1; i < len; i++) {
			chalk[i] = chalk[i] + chalk[i - 1];
			if (chalk[i] > 1000000000) {
				right = i - 1;
				break;
			}
		}
		int mod = k % chalk[right];
		int ans = -1;
		while (left <= right) {
			int m = ((right - left) >> 1) + left;
			if (chalk[m] == mod) {
				if (m + 1 < len) {
					return m + 1;
				} else {
					return 0;
				}
			} else if (mod < chalk[m]) {
				ans = m;
				right = m - 1;
			} else {
				left = m + 1;
			}
		}
		return ans;
	}

// 1,3,5,7
	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		System.out.println(Integer.MAX_VALUE);
		System.out.println(Integer.MAX_VALUE + 10000);

	}

}
